#include <iostream>
#include <vector>
#include <cmath>
#define INF 1000
using namespace std;

int main()
{
    int n, m, s;
    cin >> n >> m >> s;
    vector<vector<int>> g(n + 1, vector<int>(n + 1, INF));
    int a, b, w;
    int minw, i, j, u;
    for (i = 0; i < m; i++)
    {
        cin >> a >> b >> w;
        g[a][b] = w;
    }

    int v = s;
    vector<int> dist = g[v]; // v到达其余顶点的最短路径
    dist[v] = 0;
    vector<int> set(n + 1, 0); // 标记数组

    set[v] = 1;

    for (i = 0; i < n - 1; ++i)
    {
        minw = INF;

        // 找到当前距离原点最近的一个点
        for (j = 1; j <= n; ++j)
        {
            if (set[j] == 0 && dist[j] < minw)
            {
                u = j;
                minw = dist[j];
            }
        }

        set[u] = 1; // 并入最短路径
        // 以刚才并入的点为中间点，更新剩余顶点的最短路径
        for (j = 1; j <= n; ++j)
        {
            if (set[j] == 0 && dist[u] + g[u][j] < dist[j])
                dist[j] = dist[u] + g[u][j];
        }
    }
    for (int i = 1; i <= n; ++i)
        cout << dist[i] << ' ';
    
    cout << endl;

    return 0;
}